1. Field of the Invention
The present invention relates to rendering devices and, more specifically, to rendering devices which go through a rendering process of generating image data representing polygons for display on display devices.
2. Description of the Background Art
Rendering processes are found in many documents, e.g., Yamaguchi, Fujio: A Unified Approach to Interference Problems Using a Triangle Processor, Proceeding of SIGGRAPH '85, July 1985. FIG. 11 is a block diagram showing the basic structure of a conventional rendering device CUrend. The rendering device CUrend of FIG. 11 includes a polygon data storage section 701, a concave polygon determination section 702, a first triangulate section 703, a second triangulate section 704, a triangle rendering section 705, and a display section 706.
Described below is the operation of such a conventional rendering device CUrend. The polygon data storage section 701 stores several pieces of polygon data Dpoly. One piece of polygon data Dpoly includes at least n (where n is a natural number of 3 or larger) sets of vertex coordinates P1 to Pn so that a polygon P is rendered. Here, the vertex coordinates P1 to Pn are two-dimensional (2D) or three-dimensional (3D) coordinates. If being 3D coordinates, all of the vertex coordinates P1 to Pn need to be located on a single plane. The polygon data Dpoly sometimes accompany various other information together with the vertex coordinates P1 to Pn. Such additional information will be described later as appropriate.
The concave polygon determination section 702 receives the polygon data Dpoly from the polygon data storage section 701. In the case that the vertex coordinates P1 to Pn included in the polygon data Dpoly are 3D, a similarity transformation process is applied onto a predetermined 2D plane (hereinafter, xy plane) Ft.
Assuming now that the polygon data Dpoly includes n sets of vertex coordinates describing the polygon P, i.e., P1 (xl, yl, zl), P2(x2, y2, z2), . . . , Pn(xn, yn, zn). In the similarity transformation process, the concave polygon determination section 702 first calculates a normal vector N to the polygon P. If the derived normal vector N is parallel to the z-axis, every z coordinate of the vertex coordinates P1 to Pn is changed in value to 0. The resultant vertex coordinates Q1(x1, yl, O) to Qn(xn, yn, O) represent the polygon P orthogonally projected onto the xy plane Ft.
As to the similarity transformation process for the case where the normal vector N is not parallel to the z-axis, FIG. 12 is referred to. In such a case, the concave polygon determination section 702 finds an intersection line L of the xy plane Ft and a plane Fp which includes the polygon P. Also, found is an angle α between the xy plane Ft and the plane Fp. After finding the intersection line L and the angle α, the concave polygon determination section 702 rotates the vertex coordinates P1 (xl, yl, zl) to Pn(xn, yn, zn) on the plane Fp about the linear intersection line L by the angle α. As a result, vertex coordinate set group Q′1(x′1, y′1, 0) to Q′n(x′n, y′n, O) are derived.
As is evident from the above description, the group of the vertex coordinates Q1(x1, y1, 0) to Qn(xn, yn, O), orthe group of the vertex coordinates Q′1(x′1, y′1, 0) to Q′n(x′n, y′n, 0) represents a polygon Q. Described below is a process to be applied to the polygon Q representedby the group of the vertex coordinates Q′1 to Q′n. Here, this process is the same to the polygon Q represented by the group of the vertex coordinates Q1 to Qn, and thus is not described.
The concave polygon determination section 702 goes through a concave-convex determination process to determine whether the polygon Q is a concave polygon or not. FIG. 13 is a diagram in assistance of explaining an exemplary concave-convex determination process. Note that, although n is exemplarily 6 in the above similarity transformation process, now in the concave-convex determination process, n is presumably 4 for convenience.
In the concave-convex determination process, the concave polygon determination section 702 first calculates 3D vectors V1(a1, b1, c1) to Vn(an, bn, cn) representing 1st to nth polygon edges of the polygon Q. As to those 3D vectors V1 to Vn, their z components c1 to cn are all 0. The 3D vector V1(a1, b1, c1) can be calculated from the vertex coordinates Q′1 and Q′2, and is equal to (x′2−x′1, y′2−y′1, 0). In the case where 2<=i<=n−1, the 3D vector Vi(ai, bi, ci) can be calculated from the vertex coordinates Q′1 and Q′(i+1), and is equal to (x′(i+1)−x′i, y′(i+1)−y′i, 0). In the case where i=n, the 3D vector Vn(an, bn, cn) can be calculated from the vertex coordinates Q′n and Q′1, and is equal to (x′1−x′n, y′1−y′n, 0).
After calculating all of the 3D vectors V1 to Vn, the concave polygon determination section 702 calculates, sequentially, an outer product of any two vectors of polygon edges of the polygon Q intersecting with each other, i.e., V1×V2, V2×V3, . . . , V(n−1)×Vn, Vn×V1. If z components of the resultant outer product vectors V1×V2, V2×V3, . . . , V(n−1)×Vn, Vn×V1 show the same negative or positive sign, or 0, the concave polygon determination section 702 determines that the polygon Q is a convex polygon, otherwise a concave polygon.
The polygon Q is the one projected the polygon P onto the xy plane Ft. Therefore, if the polygon Q is determined as being a convex polygon, the concave polygon determination section 702 determines that the polygon P is also a convex polygon, and passes the polygon data Dpoly received from the polygon data storage section 701 to the first triangulate section 703. On the other hand, if the polygon P is determined as being a concave polygon, the polygon data Dpoly is forwarded to the second triangulate section 704.
Here, in the case where the polygon data Dpoly includes any additional information indicating the concave-convex attribute of the polygon P, the concave polygon determination section 702 does not go through the concave-convex determination process utilizing outer products, but refer to the concave-convex attribute to determine whether the polygon Q, i.e., polygon P, is a concave polygon.
To the received polygon data Dpoly, the first triangulate section 703 applies a first triangulate process so that the convex polygon P is represented by a plurality of independent triangles. In the first triangulate process, the first triangulate section 703 selects 3 sets of the vertex coordinates P1, P2, and P3 from the polygon data Dpoly to generate triangle data Dtril. Conceptually, the convex polygon P is divided into ΔP1 P2 P3 structured by the vertex coordinates P1, P2, and P3. In the below, Δ denotes a triangle. For example, ΔP1 P2 P3 represents a triangle structured by the vertex coordinates P1, P2, and P3.
Next, the first triangulate section 703 selects 3 sets of the vertex coordinates, this time, P1, P3, and P4, to generate triangle data Dtri2. Thereafter, when 3<=i<=n−2, the first triangulate section 703 selects in the same manner 3 sets of the vertex coordinate sets P1, P(i+1), and P(i+2) so as to generate triangle data Dtri3 to Dtri (n−2). Conceptually, the convex triangle P is divided into (n−2) pieces of triangles. The resultant (n−2) pieces of triangle data Dtril to Dtri (n−2) are passed to the triangle rendering section 705. Here, when the received polygon data Dpoly includes additional information, the first triangulate section 703 also passes it to the triangle rendering section 705.
The second triangulate section 704 retains the polygon data Dpoly coming from the concave polygon determination section 702, and applies thereto a second triangulate process so that the concave polygon P is represented by a plurality of independent triangles. FIG. 14 shows the procedure of the second triangulate process. In FIG. 14, the second triangulate section 704 checks the vertexes of the concave polygon P for which vertex type, i.e., a concave vertex or a convex vertex, and counts the number Nc of the concave vertexes (step S1001). Here, the concave vertex means a vertex of the concave polygon P with an interior angle exceeding 180 degrees. Conversely, the convex vertex means a vertex with an interior angle smaller than 180 degrees.
In step S1001, in more detail, carried out first is the same process as the concave-convex determination process performed by the concave polygon determination section 702. That is, the second triangulate section 704 calculates, sequentially, an outer product of any two vectors, i.e., polygon edges, extending from one vertex Pi (where i=1, 2, . . . , n) of the concave polygon P. The current vertex Pi is then checked for its vertex type based on the z component of the calculated outer product, i.e., which sign the z component is showing. If the z component is showing 0, either of the vertex types is applicable to the vertex Pi.
After checking all of the z components of the outer products, the second triangulate section 704 counts the number Nc of the concave vertexes. The procedure then goes to step S1002. Here, in the below discussion, the vertex Pi determined as being the concave vertex in step S1001 is referred to as a concave vertex CPi, otherwise a convex vertex VPi.
In the case where the number Nc is not 0 in step S1002, the second triangulate section 704 selects one convex vertex VPi from those others as a reference vertex Pb (step S1003). Then, the second triangulate section 704 selects, from the vertex coordinates P1 to Pn, two sets of vertex coordinates Pk and Pj (where k=1, 2, . . . n, j=1, 2, . . . , n, and k≠j) adjacent to the reference vertex Pb. Accordingly, the second triangulate section 704 forms a partial triangle ΔPb Pk Pj with the reference vertex Pb, and the vertexes Pk and Pj (step S1004).
The second triangulate section 704 then determines whether there are any other vertexes P1 to Pn in the partial triangle ΔPb Pk Pj (step S1005).
If determined Yes, the second triangulate section 704 regards the image data Dimage which will be generated by the triangle rendering section 705 as not representing the polygon P correctly. In other words, the partial triangle ΔPb Pk Pj formed in step S1004 is regarded as not being usable for rendering the polygon P correctly. The procedure thus returns to step S1003. The second triangulate section 704 selects again this time another convex vertex VPi which is not yet selected from those others as the reference vertex Pb (step S1003). The procedure then goes through steps S1004 and S1005.
On the other hand, if determined in step S1005 that there is no other vertexes P1 to Pn, the second triangulate section 704 regards the partial triangle ΔPb Pk Pj formed in step S1004 as being usable for rendering the polygon P correctly. The procedure then goes to step S1006. The second triangulate section 704 generates and retains triangle data Dtri which represents the partial triangle ΔPb Pk Pj formed by the vertexes Pb, Pk, and Pj (step S1006).
The second triangulate section 704 then determines whether polygon data Dpoly' can be generated from the polygon data Dpoly which is currently at hand (step S1007). To be more specific, from the polygon data Dpoly, the second triangulate section 704 eliminates the reference vertex coordinates Pb selected in step S1003. If there are no more vertexes left, the second triangulate section 704 determines that the polygon data Dpoly' cannot be generated so that the procedure goes to step S1010. Then, the second triangulate section 704 forwards, to the triangle rendering section 705, at least one triangle data Dtri generated in step S1006. In the case where the originally-received polygon data Dpoly includes any additional information, the second triangulate section 704 also passes it to the triangle rendering section 705.
On the other hand, if there are any vertexes left after eliminating the reference vertex coordinates Pb, the polygon data Dpoly' is determined as being generable so that the procedure goes to step S1008. Accordingly, the second triangulate section 704 generates the polygon data Dpoly'. As such, the resultant polygon P′ represented by the polygon data Dpoly' is the one formed by the vertexes P1 to Pn of the polygon P except for the reference vertex Pb.
The second triangulate section 704 then sets the generated polygon data Dpoly' as the polygon data Dpoly(step S1008), and the procedure returns to step S1001. In step S1001 this time, the second triangulate section 704 counts the number Nc of the concave vertexes CPi of the polygon P′. Thereafter, the second triangulate section 704 determines if the number Nc is 0 or not, and if not 0, the procedure goes through steps S1003 to S1008 with the newly-set polygon data Dpoly.
If the number Nc is 0, the polygon P′ is determined as being a convex polygon, and the second triangulate section 704 applies the first triangulate process to the polygon P′ (step S1009) Assuming that the number of vertexes of the polygon P′ is Nv, the second triangulate section 704 resultantly generates (Nv−2) pieces of triangle data Dtril to Dtri(Nv−2).
The second triangulate section 704 forwards, to the triangle rendering section 705, at least one triangle data Dtri generated in step S1006, and (Nv−2) pieces of triangle data Dtril to Drti (Nv−2) generated in step S1009 (step S1010). In the case where the originally-received polygon data Dpoly includes any additional information, the second triangulate section 704 also passes it to the triangle rendering section 705.
As such, the triangle rendering section 705 receives various pieces of triangle data Dtri from the first triangulate section 703 or the second triangulate section 704. The triangle rendering section 705 may also receive any additional information about the polygon data Dpoly. The triangle rendering section 705 follows the additional information, specifically color information included therein, to color-fill a region formed by 3 sets of vertex coordinates Pr (where r=1, 2, . . . , n), Ps (where s=1, 2, . . . , n), and Pt (where t=1, 2, . . . , n, but r≠s≠t) included in one of the received triangle data Dtri. Thereafter, until no triangle data Dtri is left at hand, the triangle rendering section 705 repeats such a rendering process as color-filling the region formed by three sets of the vertex coordinates Pr, Ps, and Pt. As a result, the image data Dimage representing the polygon P is generated in the internal memory of the triangle rendering section 705. In accordance with thus generated image data Dimaqe, the display section 706 applies a display process so that the polygon P is displayed on its screen.
As such, in the conventional rendering device CUrend, the triangle rendering section 705 applies the rendering process on a triangle basis to the polygon data Dpoly. This results in several pieces of triangle data Dtri from the polygon data Dpoly. The problem here is that the larger the number of vertexes of the polygon P to be rendered, the greater the number of triangle data Dtri to be generated. As a result, the time taken for the triangle rendering section 705 to go through the rendering process becomes longer.
Especially, if the polygon P is a concave polygon, the second triangulate process (see FIG. 14) is required, which is not as simple as the first triangulation process. Therefore, it takes a greater amount of time for the conventional rendering device CUrend to render the concave polygon P.